/**
 * 反转单链表
 */

// 迭代
function LinkNode(){
    this.node = node
    this.next = null
}
function reverseLinkNode(head) {

    if(!head) return null;

    while(head) {
        let temp= new LinkNode()
        // 记住链表本来的下一个节点
        // 转圈圈， 合成一个圈
        temp = node.next;
        // 将下一个点往后推一个
        node.next = next;
        next = node
        node = temp;
    }
}

// 递归实现
function reverseLinkNodeV2(head){
    if(!head) return null
    let cur = reverseLinkNode(head.next)
    head.next.next = head
    head.next = null
    return  cur;
}


// 栈实现
function reverseLinkNodeV3(head){
    if(!head) return null
    const stack = []

    // 先将所有的节点都塞进栈中。
    while (head) {
        stack.push(head)
        head.next = head
    }

    if(stack.length ===0) return null

    // 如果栈的长度不为0， 就返回第一个元素为新链表的头
    let newHead = stack.pop()

    // 当剩下的栈长度还有， 那就依次取出， 然后， 记住队头需要往后移动一个。
    while(stack.length !== 0) {
        newHead.next = stack.pop()
        newHead = newHead.next
    }
    newHead.next = null;
}
